package leetcode.weekly.week338;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	List<List<Integer>> nexts;

	int[] coins;
	int ret;
	int[] ans;
	int[] d1, d2;

	public int collectTheCoins(int[] coins, int[][] edges) {
		this.coins = coins;
		int n = coins.length;
		ans = new int[n];
		d1 = new int[n];
		d2 = new int[n];
		for (int i = 0; i < n; i++) {
			d1[i] = coins[i] == 1 ? 0 : -1;
			d2[i] = coins[i] == 1 ? 0 : -1;
		}
		nexts = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int[] e : edges) {
			int a = e[0], b = e[1];
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		f1(0, -1);
		ret = Integer.MAX_VALUE;
		f2(0, -1);
		return ret;
	}

	private void f2(int root, int parent) {
		if (ans[root] != Integer.MIN_VALUE) {
			ret = Math.min(ret, ans[root]);
		}
		List<Integer> next = nexts.get(root);
		for (int nxt : next) {
			if (nxt != parent) {
				int t1 = ans[root], t2 = ans[nxt], t3 = d1[nxt], t4 = d2[nxt], t5 = d1[root], t6 = d2[root];
				if (ans[nxt] != Integer.MAX_VALUE) {
					ans[root] -= ans[nxt];
				}
				if (d1[nxt] >= 2) {
					ans[root] -= 2;
				}
				if (ans[root] != Integer.MAX_VALUE) {
					ans[nxt] += ans[root];
				}
				if (d1[root] != d1[nxt] + 1) {
					if (d1[root] >= 2) {
						ans[nxt] += 2;
					}
					if (d1[root] + 1 > d1[nxt]) {
						d2[nxt] = d1[nxt];
						d1[nxt] = d1[root] + 1;
					} else if (d1[root] + 1 > d2[nxt]) {
						d2[nxt] = d1[root] + 1;
					}
				} else {
					if (d2[root] >= 2) {
						ans[nxt] += 2;
					}
					if (d2[root] + 1 > d1[nxt]) {
						d2[nxt] = d1[nxt];
						d1[nxt] = d2[root] + 1;
					} else if (d2[root] + 1 > d2[nxt]) {
						d2[nxt] = d2[root] + 1;
					}
				}
				f2(nxt, root);
				ans[root] = t1;
				d1[root] = t5;
				d2[root] = t6;
				ans[nxt] = t2;
				d1[nxt] = t3;
				d2[nxt] = t4;
			}
		}
	}

	private void f1(int root, int parent) {
		List<Integer> next = nexts.get(root);
		for (int nxt : next) {
			if (nxt != parent) {
				f1(nxt, root);
				if (ans[nxt] != Integer.MAX_VALUE) {
					ans[root] += ans[nxt];
				}
				if (d1[nxt] >= 2) {
					ans[root] += 2;
				}
				if (d1[nxt] != -1) {
					if (d1[nxt] + 1 > d1[root]) {
						d2[root] = d1[root];
						d1[root] = d1[nxt] + 1;
					} else if (d1[nxt] + 1 > d2[root]) {
						d2[root] = d1[nxt] + 1;
					}
				}
				if (d2[nxt] != -1) {
					if (d2[nxt] + 1 > d2[root]) {
						d2[root] = d2[nxt] + 1;
					}
				}
			}
		}
		if (ans[root] == 0) {
			ans[root] = Integer.MAX_VALUE;
		}
	}
}
